package dp.一维数组;


import java.util.Arrays;

/**
 * https://leetcode.cn/problems/house-robber-ii/
 *
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 *
 * 题解：https://mp.weixin.qq.com/s/4WdYW4m4LFtLvXqCrYHW_w
 */
public class _213_打家劫舍II {
    public static void main(String[] args) {
        int[] nums = new int[]{2,3,2};
        _213_打家劫舍II _213_打家劫舍II = new _213_打家劫舍II();
        int result = _213_打家劫舍II.rob(nums);
        System.out.println(result);
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        meno1 = new int[nums.length];
        meno2 = new int[nums.length];
        Arrays.fill(meno1, -1);
        Arrays.fill(meno2, -1);
        return Math.max(
                dp(nums, 0, nums.length - 1, meno1),
                dp(nums, 1, nums.length, meno2));
    }

    int[] meno1;
    int[] meno2;

    private int dp(int[] nums, int start, int end, int[] meno) {
        if (start >= end) return 0;

        if (meno[start] != -1) {
            return meno[start];
        }

        meno[start] = Math.max(
                nums[start] + dp(nums, start + 2, end, meno),
                dp(nums, start + 1, end, meno));

        return meno[start];
    }
}
